Data networks use an assortment of switches, routers and traffic links to distribute the transmission of data. Many modern network switches and routers employ interconnection network consisting of multi-staged ATM (asynchronous transfer mode) switching elements (in a switch fabric) to provide fast speed and high bandwidth data transmission capabilities. Each switching element has multiple input and output ports, and a data path controller (DPC) with a configured switch lookup table. When an encapsulated packet arrive on a given input port, the switching element does a table lookup by using the packet header information to decide on which of its output port this packet should be sent out. To increases the number of input/output ports needed by a router system, a switch fabric layout consists of multiple switching elements in several stages, which are interconnected by physical links or buses. Under a physical link, the data packet can utilize multiple virtual circuit paths by putting different virtual circuit identification (VCI) in its encapsulated ATM header.
A challenge in developing such systems is to assign the virtual circuit paths, or the virtual circuit identification (VCI) mapping to each switching element's lookup table to maximize the utilization and throughput of the interconnection network and to satisfy any specific traffic pattern requirements for the network overall. For example, a traffic path conflict may occur within an interconnection network. Such conflicts can occur when input traffic from two different input source ports uses the same physical link on one data path controller (DPC) to two different output destination ports. A conflict means that these two traffic paths, even for different input and output port pairs, cannot be utilized simultaneously to provide full bandwidth because of the contention on the same physical link in the switch fabric.
In one known router configuration, the router has 128 input ports that act as points of “ingress” and 128 output ports that act as points of “egress” of the router. From the ingress side to the egress side of the router, the distribution of the data paths is often allocated such that the data is transmitted unevenly and so that the data traffic will heavier on certain virtual paths. This often results in a bottleneck of the data within the router. Compounding this problem is the inclusion of switching elements with varying data transmission speeds. In addition, these switching elements may require that data be split into various multiple paths for proper operation.
For example, with many modern-day router system architectures, data is routed using an allocation scheme that supports a single-port high-speed board communicating with a multiple-port low-speed board. Thus, data traffic arrived from all the ports of the low speed board may be aggregated into the single-port high-speed board by multiple paths in parallel without conflicts. Similarly, traffic arrived from a high-speed port may be de-aggregated into multiple ports of a given low speed board. Furthermore, to support communications between two high-speed switching elements, the traffic may have to be split evenly into smaller multiple paths (or “stripes”) and sent to multiple ports in a first stage. Through multiple non-conflict paths, which are pre-allocated in the interconnection network, traffic must then be aggregated in a last stage to a desired output port. Dividing and reassembling the data into the required multiple paths for the various boards can lead to conflicts in the routing of the data that can result in severe congestion and packet lose.
Therefore, what is needed is a method to design the system in which traffic between source and destination ports is evenly transmitted through multi-staged switching elements in the switch fabric, and no conflict arises during the paths of the transmitted data.